package data.structure.line;

/**
 * 稀疏数组
 */
public class SparseArray {

    public static void main(String[] args) {
        int[][] a = new int[9][9];
        a[3][0] = 1;
        a[0][1] = 2;
        print(a);

        System.out.println("开始转换成稀疏数组");

        int[][] sparse = toSparse(a);
        print(sparse);
        System.out.println("完成转换");


        System.out.println("开始转换成常规数组");
        int[][] array = toArray(sparse);
        print(array);
        System.out.println("完成转换");
    }

    /**
     * 普通二维数组 转 稀疏数组
     * @param arr
     * @return
     */
    public static int[][] toSparse(int[][] arr) {
        int valCount = 0;
        int rowLength = arr.length;
        int colLength = arr[0].length;
        for (int[] ints : arr) {
            for (int c = 0; c < colLength; c++) {
                if (ints[c] != 0) {
                    valCount++;
                }
            }
        }
        int[][] sparseArray = new int[valCount + 1][3];
        int index = 1;
        sparseArray[0][0] = rowLength;
        sparseArray[0][1] = colLength;
        sparseArray[0][2] = valCount;
        out:
        for (int r = 0; r < rowLength; r++) {
            for (int c = 0; c < colLength; c++) {
                if (arr[r][c] != 0) {
                    sparseArray[index][0] = r;
                    sparseArray[index][1] = c;
                    sparseArray[index][2] = arr[r][c];
                    if (index++ >= valCount) {
                        break out;
                    }
                }
            }
        }
        return sparseArray;
    }

    /**
     * 稀疏数组 转 普通二维数组
     * @param arr
     * @return
     */
    public static int[][] toArray(int[][] arr) {
        // 系数数组第一行存储了 原始数组的大小 和元素个数
        // 创建原始数组
        int[][] array = new int[arr[0][0]][arr[0][1]];
        // 元素个数
        int rowLength = arr[0][2];
        // 遍历赋值
        for (int i = 1; i < rowLength + 1; i++) {
            array[arr[i][0]][arr[i][1]] = arr[i][2];
        }
        return array;
    }

    private static void print(int[][] a) {
        for (int[] row : a) {
            for (int val : row) {
                System.out.printf("%d\t", val);
            }
            System.out.println();
        }
    }

}
